207 课程表

https://leetcode.cn/leetbook/read/top-interview-questions-hard/xd54x2/

cost: 22m46s

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, unordered_set<int>> deps;
        for (const auto item : prerequisites) {
            deps[item[0]].insert(item[1]);
        }
        for (const auto [course, vec] : deps) {
            if (!visited.count(course)) {
                bool ok = this->dfs(deps, course);
                if (!ok) {
                    return false;
                }
            }
        }
        return true;
    }

private:
    bool dfs(unordered_map<int, unordered_set<int>>& deps, int course) {
        if (currDeps.count(course)) {
            return false;
        }
        if (visited.count(course)) {
            return true;
        }
        visited.insert(course);
        for (const int dep : deps[course]) {
            currDeps.insert(course);
            bool ok = this->dfs(deps, dep);
            currDeps.erase(course);
            if (!ok) {
                return false;
            }
        }
        return true;
    }
    unordered_set<int> visited;
    unordered_set<int> currDeps;
};